package algorithms.leaning.class08;

import common.util.MyUtil;

/**
 * 桶为0-9
 * 数据范围有限，比如人的年龄排序
 * 数值范围 0-150
 *
 * @author guichang
 * @date 2021/6/5
 */

@SuppressWarnings("all")
public class Code2_桶排序_计数排序 {

    public static void main(String[] args) {
        int[] array = MyUtil.createRandomArray(100, 0, 150);
        countSort(array);
        MyUtil.printInt(array);
    }

    public static void countSort(int[] array) {
        // 边界条件
        if (array == null || array.length <= 1) {
            return;
        }
        // 辅助数组，存着每个数字出现的个数
        int[] helpArray = new int[151];
        for (int i = 0; i < array.length; i++) {
            helpArray[array[i]]++;
        }
        // 新array的索引
        int index = 0;
        // 遍历一边help数组替换array
        for (int i = 0; i < helpArray.length; i++) {
            if (helpArray[i] > 0) {
                for (int j = 1; j <= helpArray[i]; j++) {
                    array[index++] = i;
                }
            }
        }
    }


}